package binaryTree;

import java.util.Stack;

public class TrimBST {
	//自己写的，未按照波哥教的递归处理思路
	public TreeNode dfs1(TreeNode root,int low,int high) {
		if(root==null) return root;
		TreeNode leftBST=dfs1(root.left,low,high);
		TreeNode rightBST=dfs1(root.right,low,high);
		if(root.val>low&&root.val<high) {
			root.left=leftBST;
			root.right=rightBST;
		}
		else if(root.val<low) {
			return rightBST;
		}
		else if(root.val>high) {
			return leftBST;
		}
		else if(root.val==low) {
			root.left=null;
			root.right=rightBST;
		}
		else if(root.val==high) {
			root.right=null;
			root.left=leftBST;
		}
		return root;
	}
	
	//改进版，按照波哥的递归处理思路
	public TreeNode dfs2(TreeNode root,int low,int high) {
		if(root==null) return null;
		if(root.val<low) {
			return dfs2(root.right,low,high);
		}
		if(root.val>high) {
			return dfs2(root.left,low,high);
		}
		root.left=dfs2(root.left,low,high);
		root.right=dfs2(root.right,low,high);
		return root;
	}
	public TreeNode trimBST(TreeNode root, int low, int high) {
        return dfs2(root,low,high);
    }
}
